package LCR剑指.LCR077;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {
    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    private ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) {
            return null;
        }
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode fast=head,slow=head;
        while (fast!=tail) {
            fast=fast.next;
            slow=slow.next;
            if (fast !=tail) {
                fast=fast.next;
            }
        }
        ListNode mid=slow;
        ListNode list1=sortList(head,mid);
        ListNode list2=sortList(mid,tail);
        ListNode newHead=mergeTwoLists(list1,list2);
        return newHead;
    }

    //合并两个有序子链表
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode temp=dummy;
        ListNode temp1=l1,temp2=l2;
        while (temp1 != null && temp2 != null) {
            if (temp1.val < temp2.val) {
                temp.next = temp1;
                temp1=temp1.next;
                temp=temp.next;
            }else {
                temp.next = temp2;
                temp2=temp2.next;
                temp=temp.next;
            }
        }
        if (temp1 != null) {
            temp.next = temp1;
        }else if (temp2 != null) {
            temp.next = temp2;
        }
        return dummy.next;
    }
}